package swardToOffer.method_2_sort_or_find.find;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Author ChanZany
 * @Date 2021/5/26 16:18
 * @Version 1.0
 * <p>
 * 面试题57（二）：和为s的连续正数序列
 * 题目：输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。
 * 例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出3个连续序列1～5、4～6和7～8。
 * 解法1:
 * 由于是求连续序列的和等于目标值,又因为所给序列为连续正数,
 * 所以该连续序列的左右边界都一定小于目标值,基于此,我们可以从左往右进行试探
 * 同样采用双指针的解法 i为左指针,初始化为0,j为右指针,初始化为i+1
 * 当sum=nums[i]+nums[j]<target时,我们先右移j,使得sum>=target
 * 当sum>=target时,再右移i,使得sum<=target
 * 重复上诉步骤,可以找到第一条连续正数序列
 * 基于第一条连续正数序列和连续正数序列的性质,将i++,然后重复上诉上诉步骤可以找到第二条序列和第n条序列
 * <p>
 * 解法2:
 * 对于目标target，若其为连续m个整数之和，则存在起始数x，有：
 * x + (x + 1) + ... + (x + m - 1) == target => m * x + m * (m - 1) / 2 == target
 * 根据这个等式，遍历m，找到符合的x即可获得相关序列
 * 譬如说如果有两个连续的数之和等于target，那么相差为1， (target - 1) % 2 == 0， 且数组一定是从 (target - 1) / 2开始的，数组的元素就是2个；
 * 如果是3个连续的数组，那么三个数之间相差为1、2，(target - 1 - 2) % 3 == 0，且数组一定是从 (target - 1 - 2) / 3开始的，数组元素是3个，
 * 依次类推，但是注意target必须是大于0的数，且res需要倒序。
 */
public class ContinuousSquenceWithSum {
    public int[][] findContinuousSequence2(int target) {
        List<int[]> result = new ArrayList<>();
        int i = 1;
        while (target > 0) {
            target -= i++;
            if (target > 0 && target % i == 0)
            {
                int[] array = new int[i];
                for (int k = target / i, j = 0; k < target / i + i; k++, j++) {
                    array[j] = k;
                }
                result.add(array);
            }
        }
        Collections.reverse(result);
        return result.toArray(new int[0][]);
    }


    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList<>();
        int i = 1, j = 1;
        while (j <= target / 2 + 1) {
            int sum = getSum(i, j);
            if (target == sum) {
                int[] tmp = new int[j - i + 1];
                for (int k = i; k <= j; k++) {
                    tmp[k - i] = k;
                }
                res.add(tmp);
                i++;
            }
            if (target > sum) j++;
            if (target < sum) i++;
        }
        return res.toArray(new int[0][0]);

    }

    private int getSum(int i, int j) {
        int sum = 0;
        for (int k = i; k <= j; k++) {
            sum += k;
        }
        return sum;
    }

    public static void main(String[] args) {
        ContinuousSquenceWithSum Main = new ContinuousSquenceWithSum();
        Main.findContinuousSequence2(15);
    }
}
